#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
#include <map>

using std::string;
using std::vector;

static void println()
{
    std::cout << std::endl;
}
template <class T, class... Args>
static void println(T o, Args... rest)
{
    std::cout << o << " ";
    println(rest...);
}

class RSA {
    using KeyPair = std::map<string, std::map<string, string>>;
public:
    RSA();
    ~RSA();
    KeyPair genKey();
    vector<uint64_t> encrypt(const string& msg);
    string decrypt(const vector<uint64_t>& enc);

// private:
    bool isPrime(uint64_t num);
    uint64_t gcd(uint64_t a, uint64_t b);
    uint64_t gcdEx(uint64_t a, uint64_t b, int64_t& x, int64_t& y);
    uint64_t inv(uint64_t e, uint64_t fyn);
    uint64_t montgomery(uint64_t m, uint64_t e, uint64_t n);

    uint64_t p;  // 大素数1
    uint64_t q;  // 大素数2
    uint64_t n;  // n = p * q, n的长度就是密钥的长度
    uint64_t e = 0x10001L;  // gcd(e, Euler) = 1, e < Euler, 工业上一般直接设为65537
    uint64_t d;  // e*d mod Euler ≡ 1
};